package com.coder.algorithm.offer_2;

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

/**
 * 圆圈中最后剩下的数字
 *
 * @author yuhushuan
 * @date 2020/7/3 18:37
 */
public class _62_1_LastNumberInCircle {

    private static int lastRemaining_List(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        List<Integer> numbers = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) {
            numbers.add(i);
        }
        int current = 0;
        while (numbers.size() > 1) {
            for (int i = 1; i < m; ++i) {
                current++;
                if (current >= numbers.size()) {
                    current %= numbers.size();
                }
            }
            // 删除
            numbers.remove(current);
        }
        return numbers.get(0);
    }

    private static int lastRemaining_Recursively(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        if (n == 1) {
            return 0;
        } else {
            return (lastRemaining_Recursively(n - 1, m) + m) % n;
        }
    }

    private static int lastRemaining_Iteratively(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        int last = 0;
        for (int i = 2; i <= n; ++i) {
            last = (last + m) % i;
        }
        return last;
    }

    public static void main(String[] args) {
        // 功能测试
        // m < n
        print(5, 2);
        print(5, 3);
        // m >= n
        print(6, 6);
        print(6, 7);

        // 特殊输入测试
        print(0, 1);

        // 性能测试
        print(4000, 997);
    }

    private static void print(int n, int m) {
        System.out.println(String.format(Locale.getDefault(),
                "从 %d 个数组成的圆圈中，删除第 %d 个数字，剩下的最后一个数字为",
                n, m));
        System.out.println("循环链表：" + lastRemaining_List(n, m));
        System.out.println("递归：" + lastRemaining_Recursively(n, m));
        System.out.println("迭代：" + lastRemaining_Iteratively(n, m));
        System.out.println();
    }
}
